(function () {
	/**
	 * Utility class for sampling weighted random points on the surface of a mesh.
	 *
	 * Building the sampler is a one-time O(n) operation. Once built, any number of
	 * random samples may be selected in O(logn) time. Memory usage is O(n).
	 *
	 * References:
	 * - http://www.joesfer.com/?p=84
	 * - https://stackoverflow.com/a/4322940/1314762
	 */
  
	const _face = new THREE.Triangle();
  
	const _color = new THREE.Vector3();
  
	class MeshSurfaceSampler {
	  constructor(mesh) {
		let geometry = mesh.geometry;
  
		if (
		  !geometry.isBufferGeometry ||
		  geometry.attributes.position.itemSize !== 3
		) {
		  throw new Error(
			"THREE.MeshSurfaceSampler: Requires BufferGeometry triangle mesh."
		  );
		}
  
		if (geometry.index) {
		  console.warn(
			"THREE.MeshSurfaceSampler: Converting geometry to non-indexed BufferGeometry."
		  );
		  geometry = geometry.toNonIndexed();
		}
  
		this.geometry = geometry;
		this.randomFunction = Math.random;
		this.positionAttribute = this.geometry.getAttribute("position");
		this.colorAttribute = this.geometry.getAttribute("color");
		this.weightAttribute = null;
		this.distribution = null;
	  }
  
	  setWeightAttribute(name) {
		this.weightAttribute = name ? this.geometry.getAttribute(name) : null;
		return this;
	  }
  
	  build() {
		const positionAttribute = this.positionAttribute;
		const weightAttribute = this.weightAttribute;
		const faceWeights = new Float32Array(positionAttribute.count / 3); // Accumulate weights for each mesh face.
  
		for (let i = 0; i < positionAttribute.count; i += 3) {
		  let faceWeight = 1;
  
		  if (weightAttribute) {
			faceWeight =
			  weightAttribute.getX(i) +
			  weightAttribute.getX(i + 1) +
			  weightAttribute.getX(i + 2);
		  }
  
		  _face.a.fromBufferAttribute(positionAttribute, i);
  
		  _face.b.fromBufferAttribute(positionAttribute, i + 1);
  
		  _face.c.fromBufferAttribute(positionAttribute, i + 2);
  
		  faceWeight *= _face.getArea();
		  faceWeights[i / 3] = faceWeight;
		} // Store cumulative total face weights in an array, where weight index
		// corresponds to face index.
  
		this.distribution = new Float32Array(positionAttribute.count / 3);
		let cumulativeTotal = 0;
  
		for (let i = 0; i < faceWeights.length; i++) {
		  cumulativeTotal += faceWeights[i];
		  this.distribution[i] = cumulativeTotal;
		}
  
		return this;
	  }
  
	  setRandomGenerator(randomFunction) {
		this.randomFunction = randomFunction;
		return this;
	  }
  
	  sample(targetPosition, targetNormal, targetColor) {
		const cumulativeTotal = this.distribution[this.distribution.length - 1];
		const faceIndex = this.binarySearch(
		  this.randomFunction() * cumulativeTotal
		);
		return this.sampleFace(
		  faceIndex,
		  targetPosition,
		  targetNormal,
		  targetColor
		);
	  }
  
	  binarySearch(x) {
		const dist = this.distribution;
		let start = 0;
		let end = dist.length - 1;
		let index = -1;
  
		while (start <= end) {
		  const mid = Math.ceil((start + end) / 2);
  
		  if (mid === 0 || (dist[mid - 1] <= x && dist[mid] > x)) {
			index = mid;
			break;
		  } else if (x < dist[mid]) {
			end = mid - 1;
		  } else {
			start = mid + 1;
		  }
		}
  
		return index;
	  }
  
	  sampleFace(faceIndex, targetPosition, targetNormal, targetColor) {
		let u = this.randomFunction();
		let v = this.randomFunction();
  
		if (u + v > 1) {
		  u = 1 - u;
		  v = 1 - v;
		}
  
		_face.a.fromBufferAttribute(this.positionAttribute, faceIndex * 3);
  
		_face.b.fromBufferAttribute(this.positionAttribute, faceIndex * 3 + 1);
  
		_face.c.fromBufferAttribute(this.positionAttribute, faceIndex * 3 + 2);
  
		targetPosition
		  .set(0, 0, 0)
		  .addScaledVector(_face.a, u)
		  .addScaledVector(_face.b, v)
		  .addScaledVector(_face.c, 1 - (u + v));
  
		if (targetNormal !== undefined) {
		  _face.getNormal(targetNormal);
		}
  
		if (targetColor !== undefined && this.colorAttribute !== undefined) {
		  _face.a.fromBufferAttribute(this.colorAttribute, faceIndex * 3);
  
		  _face.b.fromBufferAttribute(this.colorAttribute, faceIndex * 3 + 1);
  
		  _face.c.fromBufferAttribute(this.colorAttribute, faceIndex * 3 + 2);
  
		  _color
			.set(0, 0, 0)
			.addScaledVector(_face.a, u)
			.addScaledVector(_face.b, v)
			.addScaledVector(_face.c, 1 - (u + v));
  
		  targetColor.r = _color.x;
		  targetColor.g = _color.y;
		  targetColor.b = _color.z;
		}
  
		return this;
	  }
	}
  
	THREE.MeshSurfaceSampler = MeshSurfaceSampler;
  })();
  